Kahn's algorithm uses in-degrees and a queue to systematically find a valid topological ordering for a Directed Acyclic Graph (DAG).
- Initialize the in-degree count for all vertices and identify starting nodes (A, B) with an in-degree of zero.
- Enqueue all zero-in-degree nodes into the processing queue: initially, the queue contains A and B.
- Dequeue a node (e.g., A), add it to the sorted list, and conceptually remove all its outgoing edges.
- Removing an edge decrements the in-degree of the neighbor node (e.g., C's in-degree drops from 2 to 1 after A is processed).
- If decrementing a neighbor's in-degree results in zero, that neighbor (C and D) is immediately enqueued for processing.
- The process repeats until the queue is empty, resulting in a complete linear ordering of all vertices.
- The final sorted list, `['A', 'B', 'C', 'D', 'E']`, represents a valid sequence of tasks or dependencies.
Kahn's Algorithm Trace Summary
| Step | Action | Queue | Sorted List | In-Degree Updates |
|---|---|---|---|---|
| 1 | Init | ['A', 'B'] | [] | {'C':2, 'D':1, 'E':2} |
| 2 | Pop 'A' | ['B'] | ['A'] | C=1 |
| 3 | Pop 'B' | ['C', 'D'] | ['A', 'B'] | C=0, D=0 |
| 4.a | Pop 'C' | ['D'] | ['A', 'B', 'C'] | E=1 |
| 4.b | Pop 'D' | ['E'] | ['A', 'B', 'C', 'D'] | E=0 |
| 5 | Pop 'E' | [] | ['A', 'B', 'C', 'D', 'E'] |